Đoàn Ủy nhiệm Y tế Công cộng Hoa Kỳ được khởi sự khi Quỹ Bệnh viện Biển được thành lập vào năm 1798 mà sau đó được tái tổ chức vào năm 1871 thành Dịch vụ Bệnh viện Biển. Dịch vụ Bệnh viện Biển có trách nhiệm chăm sóc và duy trì sức khỏe cho các thủy thủ thương mại nhưng khi Hoa Kỳ phát triển rộng lớn hơn thì sứ mệnh của nó cũng được nới rộng. Dịch vụ Bệnh viện Biển chẳng bao lâu bắt đầu mở rộng vai trò y tế bao gồm các khía cạnh y tế như bảo vệ thương mại và y tế của Hoa Kỳ. Một trong những vai trò đó là cách ly kiểm dịch.

Bác sĩ John Maynard Woodworth, bác sĩ nổi tiếng của Quân đội Liên bang tham chiến dưới quyền của tướng William Tecumseh Sherman, được bổ nhiệm làm Y sĩ Quản đốc (supervising surgeon) vào năm 1871. Chức vị của bác sĩ Woodworth sau đó được đổi thành Tổng Y sĩ Quản đốc (Supervising Surgeon General) và dần dần trở thành Tổng Y sĩ Hoa Kỳ (Surgeon General of the United States). Bác sĩ Woodworth là người có công trong việc thành lập chính thức Đoàn Ủy nhiệm Y tế Công cộng vào năm 1889. Ông đã tổ chức các nhân sự thuộc Dịch vụ Bệnh viện Biển theo cơ cấu tổ chức quân sự của Lục quân Hoa Kỳ để trở thành một lực lượng lưu động gồm các chuyên viên y tế mà có thể được phái đi phục vụ đất nước khi cần. Ông cũng lập ra các chuẩn mực bổ nhiệm và tạo ra mẫu huy hiệu của Dịch vụ Bệnh viện Biển gồm một mỏ neo và y hiệu. Sau đó cùng năm, Tổng thống Grover Cleveland đã ký thành luật việc chính thức thành lập Đoàn Ủy nhiệm Y tế Công cộng hiện đại. Lúc ban đầu đoàn chỉ nhận các y sĩ nhưng sau đó mở rộng bao gồm nha sĩ, kỹ sư môi trường, dược sĩ, y tá, chuyên viên y tế môi trường, khoa học gia và các chuyên viên y tế khác.